package io.github.hadyang.leetcode.bytedance;

/** @author haoyang.shi */
public class Link1024 {

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
      return null;
    }

    if (headA == headB) {
      return headA;
    }

    int lenA = 1;
    int lenB = 1;
    ListNode temp = headA;
    while (temp.next != null) {
      temp = temp.next;
      lenA++;
    }

    ListNode tailA = temp;

    temp = headB;
    while (temp.next != null) {
      temp = temp.next;
      lenB++;
    }

    ListNode tailB = temp;
    if (tailB != tailA) {
      return null;
    }

    if (lenA > lenB) {
      for (int i = 0; i < lenA - lenB && headA != null; i++) {
        headA = headA.next;
      }

    } else if (lenA < lenB) {
      for (int i = 0; i < lenB - lenA && headB != null; i++) {
        headB = headB.next;
      }
    }

    while (!headA.equals(headB)) {
      headA = headA.next;
      headB = headB.next;
    }

    return headA;
  }

  private static class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }

    @Override
    public String toString() {
      return "ListNode{" + "val=" + val + '}';
    }
  }

  public static void main(String[] args) {
    ListNode head1 = createListNode(4, 1);
    ListNode head2 = createListNode(5, 0, 1);
    ListNode head3 = createListNode(8, 4, 5);

    head1.next = head3;
    head2.next = head3;

    Link1024 main = new Link1024();

    System.out.println(main.getIntersectionNode(head1, head2));
    System.out.println(main.getIntersectionNode(null, null));
    System.out.println(main.getIntersectionNode(head1, head1));
  }

  private static ListNode createListNode(int... ints) {
    ListNode head = new ListNode(ints[0]);
    ListNode cur = head;
    for (int i = 1; i < ints.length; i++) {
      cur.next = new ListNode(ints[i]);
      cur = cur.next;
    }
    return head;
  }
}
